package main
import (
	"fmt"
	"os"
)
//从文件读取地图
func readMaze(fileName string)[][]int{
	file,err:=os.Open(fileName)
	if err!=nil {
		panic(err)
	}
	var row,col int
	fmt.Fscan(file,&row,&col)
	maze :=make([][]int,row)
	for i:=range maze{
		maze[i]=make([]int,col)
		for j:=range maze[i]{
			fmt.Fscan(file,&maze[i][j])
		}
	}
	return maze
}
//地图的每个点
type point struct{
	i,j int
}
//地图点的移动
func (p point)add(dir point)point{
	return point{p.i+dir.i,p.j+dir.j}
}
//判断点是不是在地图中
func (p point)at(maze [][]int)(int,bool){
	if p.i<0||p.i>=len(maze) {
		return 0 ,false
	}
	if p.j<0||p.j>=len(maze[p.i]){
		return 0,false
	}
	return maze[p.i][p.j],true
}
//四个方向
var dirs=[4]point{
	{-1,0},{0,-1},{1,0},{0,1},
}
//广度优先可走格子部署
func walk(maze [][]int,start,end point)[][]int{
	//制作一个空白表格
	step:=make([][]int,len(maze))
	for i:=range step{
		step[i]=make([]int,len(maze[i]))
	}
	//点的队列
	Q:=[]point{start}

	for	len(Q)>0{
		cur:=Q[0]
		Q=Q[1:]
		if cur ==end {
			break
		}
		for _,dir:=range dirs{
			next:=cur.add(dir)//坐标的一个方向上的一个点
			val,ok:=next.at(maze)//点在不在迷宫表格里面
			if !ok ||val==1{
				continue
			}
			val,ok=next.at(step)//点在规划表格里面有没有计算过
			if val!=0||!ok {
				continue
			}
			if next==start{
				continue
			}
			curSteps,_:=cur.at(step)
			step[next.i][next.j]=curSteps+1
			Q=append(Q,next)
		}
	}
	return step
}
//规划路劲
func mazePath(maze [][]int,start,end point)[][]int{
	mazePath:=make([][]int,len(maze))
	for i:=0;i<len(mazePath);i++{
		mazePath[i]=make([]int,len(maze[i]))
	}
	mazePath[end.i][end.j]=1
	mazePath[start.i][start.j]=1
	Que:=[]point{end}
	step:=maze[end.i][end.j]

	for len(Que)>0{
		cur:=Que[0]
		Que=Que[1:]
		if cur==start {
			break
		}
		for _,dir:=range dirs {
			next:=cur.add(dir)
			val,ok:=next.at(maze)
			if val>=step||!ok||val==0{
				continue
			}
			if val==0&&step==0 {
				continue
			}
			step=maze[next.i][next.j]
			mazePath[next.i][next.j]=1
			Que=append(Que,next)
		}
	}
	return mazePath
}

func main() {
	maze:=readMaze("maze/maze.in")
	//for _,row:=range maze{
	//	for _,val:=range row{
	//		fmt.Printf("%d ",val)
	//	}
	//	fmt.Println()
	//}
	step:=walk(maze,point{0,0},point{len(maze)-1,len(maze[0])-1})
	for i:=0;i<len(step);i++{
		for j:=0;j<len(step[i]);j++ {
			fmt.Printf("%3d",step[i][j])
		}
		fmt.Println()
	}
	fmt.Println()

	step=mazePath(step,point{0,0},point{len(step)-1,len(step[0])-1})
	for i:=0;i<len(step);i++{
		for j:=0;j<len(step[i]);j++ {
			fmt.Printf("%3d",step[i][j])
		}
		fmt.Println()
	}
}
